public class SolutionLCP4 {

    int m;

    public int domino(int n, int m, int[][] broken) {
        this.m=m;
        int[][] f=new int[n][1<<m];
        if (n==1){
            return cal(0,0,0,broken);
        }
        for (int i=0;i<1<<m;i++){
            if (can(0,i,broken)){
                f[0][i]=cal(0,0,i,broken)+Integer.bitCount(i);
            }
        }
        for (int i=1;i<n-1;i++){
            for (int j=0;j<1<<m;j++){
                if (can(i,j,broken)){
                    for (int k=0;k<1<<m;k++){
                        if (can(i-1,k,broken) && can2(j,k)){
                            f[i][j]=Math.max(f[i][j],f[i-1][k]+cal(k,i,j,broken)+Integer.bitCount(j));
                        }
                    }
                }
            }
        }
        int ans=0;
        for (int i=0;i<1<<m;i++){
            ans=Math.max(ans,f[n-2][i]+cal(i,n-1,0,broken));
        }
        return ans;
    }

    private boolean can2(int j, int k) {
        for (int i=0;i<m;i++){
            if ((j&(1<<i))>0 && (k&(1<<i))>0){
                return false;
            }
        }
        return true;
    }

    private boolean can(int x, int y, int[][] broken) {
        int[] f=new int[m];
        int[] g=new int[m];
        for (int[] ints : broken) {
            if (ints[0]==x){
                f[ints[1]]=1;
            }
            if (ints[0]==x+1){
                g[ints[1]]=1;
            }
        }
        for (int i=0;i<m;i++){
            if ((f[i]==1 || g[i]==1) && (y&(1<<i))>0){
                return false;
            }
        }
        return true;
    }

    private int cal(int k, int x, int y, int[][] broken) {
        int[] f=new int[m];
        for (int[] ints : broken) {
            if (ints[0]==x){
                f[ints[1]]=1;
            }
        }
        int ans=0;
        for (int i=0;i<m-1;i++){
            if (f[i]==0 && f[i+1]==0 && (y&(1<<i))==0 && (y&(1<<(i+1)))==0 && (k&(1<<i))==0 && (k&(1<<(i+1)))==0){
                ans++;
                i++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP4().domino(3,3,new int[][]{}));
    }
}
